package niuke;
import java.util.*;
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
public class niuKeMain11 {
    public ListNode plusOne (ListNode head) {
        // write code here
        Stack<ListNode> stack=new Stack();
        ListNode head1=head;
        while(head1!=null){
            stack.push(head1);
            head1=head1.next;
        }
        int tmp=1;
        while(!stack.isEmpty()){
            ListNode n1=stack.pop();
            tmp+=n1.val;
            n1.val=tmp%10;
            tmp=tmp/10;
        }
        ListNode n2=null;
        if(tmp>0){
            n2=new ListNode(tmp);
            n2.next=head;
            return n2;
        }
        return head;
    }
    public ListNode deleteNode (ListNode head, int val) {
        // write code here
        if(head.val==val){
            head=head.next;
            return head;
        }if(head==null){
            return null;
        }
        ListNode n1=head;
        ListNode n2=null;
        while(n1!=null&&n1.val!=val){
            n2=n1;
            n1=n1.next;
        }
        n2.next=n1.next;
        return head;
    }
    public RandomListNode Clone(RandomListNode pHead) {
        HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
        RandomListNode node=pHead;
        while (node!=null){
            map.put(node,new RandomListNode(node.label));
            node=node.next;
        }
        node=pHead;
        while (node!=null){
            map.get(node).next=map.get(node.next);
            map.get(node).random=map.get(node.random);
            node=node.next;
        }
        return map.get(pHead);
    }
//    public int TreeDepth(TreeNode root) {
//        if (root==null){
//            return 0;
//        }
//        int left=TreeDepth(root.left);
//        int right=TreeDepth(root.right);
//        return Math.max(left,right)+1;
//    }
    public String ReverseSentence(String str) {
        if (str==null){
            return null;
        }
        String str1="";
        Stack<Character> stack=new Stack<>();
        int len=str.length();
        for (int i = len-1; i>=0; i--) {
            char ch=str.charAt(i);
            if (ch!=' '){
                stack.push(ch);
            }else {
                while (!stack.isEmpty()){
                    str1+=stack.pop();
                }
                str1+=ch;
            }
        }
        while (!stack.isEmpty()){
            str1+=stack.pop();
        }
        return str1;
    }
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        int n=num.length;
        ArrayList<Integer> list=new ArrayList<>();
        if(size==0||size>n){
            return list;
        }
        for (int i = 0; i < n-size+1; i++) {
            int right=i+size;
            int max=Integer.MIN_VALUE;
            for (int j = i; j < right; j++) {
                max=Math.max(max,num[j]);
            }
            list.add(max);
        }
        return list;
    }

    public String decodeString (String s) {
        // write code here
        if (s==null){
            return null;
        }
        Stack<Integer> stack1=new Stack<>();
        Stack<String> stack2=new Stack<>();
        String str="";
        int  n=s.length();
        int num=0;
        for (int i = 0; i < n; i++) {
            char ch=s.charAt(i);
            if (Character.isDigit(ch)){
                num=num*10+ch-'0';
            }else if(Character.isLetter(ch)){
                str=str+ch;
            }else if (ch=='['){
                stack1.push(num);
                stack2.push(str);
                num=0;
                str="";
            }else {
                int num1=stack1.pop();
                String str1=stack2.pop();
                for (int j = 0; j < num1; j++) {
                    str1+=str;
                }
                str=str1;
            }
        }
        return str;
    }
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if (A==null){
            return 0;
        }
        int arr[]=new int[n];
        arr[0]=1;
        for (int i = 1; i < n; i++) {
            if (A.charAt(i)!=A.charAt(0)){
                arr[i]=arr[i-1];
            }else {
                int left=1;
                int right=i-1;
                while (left<=right){
                    if (A.charAt(left)!=A.charAt(right)){
                        arr[i]=arr[i-1];
                        break;
                    }
                    left++;
                    right--;
                }
                if (left>right){
                    arr[i]=i+1;
                }
            }
        }
        return arr[n-1];
    }
    public boolean detectCapitalUse(String word) {
        if (word==null){
            return true;
        }
        int count=0;
        int i=-1;
        int n=word.length();
        for (int j = 0; j < n; j++) {
            char ch=word.charAt(j);
            if (ch>='A'&&ch<='Z'){
                count++;
                i=j;
            }
        }
        if (count==0&&i==-1) return true;
        if (count==1&&i==0) return true;
        if (count==n) return true;
        return false;
    }
}
